package DataStructure.tree.BST;

import java.util.*;

/**
 * @author 张彬彬
 * 二分搜索树
 * 实现的功能 :
 * 1.插入元素
 * 2.前中后序遍历 广度优先遍历  递归与非递归实现
 * 3，前序遍历改写toString方法
 * 4.寻找最小值，最大值并删除最小值，最大值
 * 前序遍历又为深度优先遍历  DFS  前序非递归遍历应用到栈的数据结构
 * 中序遍历 也为排序算法
 * 后序遍历 应用在内存的释放 只有将每个节点的子节点释放掉才能释放掉该节点
 * 广度优先遍历  应用最优路线等问题  应用到队列这种数据结构实现
 */
public class BinarySearchTree<E extends Comparable<E>> {
    private Node root;
    private int size;

    public BinarySearchTree() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    //此方法是向树中添加一个元素
    public void add(E e) {
        root = add(root, e);
    }

    //递归实现遍历插入元素
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }

        if (e.compareTo(node.e) < 0) {
            node.left = add(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = add(node.right, e);
        }

        return node;
    }

    public boolean contain(E e) {
        return contain(root, e);
    }

    private boolean contain(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (e.compareTo(node.e) == 0) {
            return true;
        } else if (e.compareTo(node.e) < 0) {
            return contain(node.left, e);
        } else {  //e.compareTo(node.e) > 0
            return contain(node.right, e);
        }
    }

    //遍历每个节点都将访问三次
    //前序遍历 也为广度优先遍历 DFS

    //前序递归遍历
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }

        System.out.print(node.e + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    //前序非递归遍历

    public void preOrderNR() {
        preOrderNR(root);
    }

    private void preOrderNR(Node node) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            System.out.print(cur.e + " ");

            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
    }

    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }

        inOrder(node.left);
        System.out.print(node.e + " ");
        inOrder(node.right);
    }

    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }

        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.e + " ");
    }

    public void levelOrder() {
        levelOrder(root);
    }

    private void levelOrder(Node node) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.remove();
            System.out.print(cur.e + " ");

            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    public E minnum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is Empty");
        }
        return minnum(root).e;
    }

    private Node minnum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minnum(node.left);
    }

    public E maxnum() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is Empty");
        }
        return maxnum(root).e;
    }

    private Node maxnum(Node node) {
        if (node.right == null) {
            return node;
        }
        return maxnum(node.right);
    }

    public E removeMin() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is Empty");
        }
        E ret = minnum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return node.right;
        }
        node.left = removeMin(node.left);
        return node;
    }


    public E removeMax() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is Empty");
        }
        E ret = maxnum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public void remove(E e) {
        root = remove(root,e);
    }

    private Node remove(Node node,E e) {
        if(node == null) {
            return null;
        }

        if(e.compareTo(node.e) < 0) {
            node.left = remove(node.left,e);
            return node;
        } else if(e.compareTo(node.e) > 0) {
            node.right = remove(node.right,e);
            return node;
        } else {
            if(node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            if(node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            Node successor = minnum(node.right);
            //此处应该先改变后继节点的右子树 再改变其左子树
            //如果先改变左子树那对于removeMin操作将导致大问题
            /////////////////       比如若删除元素5 successor指向6这个节点
            //      5      //       若先执行269处的代码即修改了这颗树的内容导致结果错误
            //    /   \    //       即对于268行删除的最小元素不是6 而是2 因为节点6多了左子树
            //   3     6   //
            //  / \     \  //
            // 2  4      8 //
            /////////////////
            successor.right = removeMin(node.right);
            successor.left = node.left;

            node.left = node.right = null;
            return successor;
        }
    }

    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        generateBSTString(root, 0, str);
        return str.toString();
    }

    private void generateBSTString(Node node, int depth, StringBuilder str) {
        if (node == null) {
            str.append(generateDepthString(depth) + null + "\n");
            return;
        }
        str.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, str);
        generateBSTString(node.right, depth + 1, str);

    }

    private String generateDepthString(int depth) {
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            str.append("-");
        }
        return str.toString();
    }

    /**
     * 树中的节点类
     */
    private class Node {
        public E e;
        public Node left;
        public Node right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }
}
